package com.buddy.leetcode._05;

/**
 * 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
 * 示例 1：
 *      输入: "babad"
 *      输出: "bab"
 * 注意: "aba"也是一个有效答案。
 * 示例 2：
 *      输入: "cbbd"
 *      输出: "bb"
 */
public class LongestPalindromicSubstring {

    /**
     * FIXME 01 中心扩展算法
     * 回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1个这样的中心。
     * 注，不是n，因为所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba”的中心在两个 b’之间）。
     * 如果s=cbbebb
     * 中心点 3
     * left =
     * @param s 字符串
     * @return
     */
    public static String myLongestPalindrome(String s) {
        int start =0,end = 0;//start回文串的开始位置，end回文串的结束位置
        for (int i=0;i<s.length();i++){
            int oddLen = expandAroundCenter(s,i,i);//回文串长度是奇数；
            int evenLen = expandAroundCenter(s,i,i+1);//回文串长度是偶数
            int len = Math.max(oddLen,evenLen);
            //保证遍历的过程中，是最长的回文串
            if (len > end - start){
                start = i-(len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start,end+1);
    }

    /**
     *  从字符串的某位置开始扩展，left为向左方向走的索引，right为向右走的索引
     * @param s 字符串
     * @param start 开始位置 = 最初的left
     * @param end 结束为止 = 最初的right
     * @return 回文串的长度
     */
    private static int expandAroundCenter(String s, int start, int end) {
        int left = start,right = end;
        while (left>=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right-start-1;
    }

    /**
     * FIXME 中心扩展算法
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        String result = "";
        String temp = "";
        for (int i=0;i<chars.length;i++){
            temp = getAouuned(chars,i,i);//回文串长度是奇数；
            //保证遍历的过程中，是最长的回文串
            if (result.length() < temp.length()){
                result = temp;
            }
            temp = getAouuned(chars,i,i+1);//回文串长度是偶数
            //保证遍历的过程中，是最长的回文串
            if (result.length() < temp.length()){
                result = temp;
            }
        }
        return result;
    }

    private static String getAouuned(char[] chars, int start, int end) {
        int length = chars.length;
        while (start >= 0 && end < length && chars[start] == chars[end]){
            start --;
            end ++;
        }
        //当初始 start = 0的时候，start-- 了，因此要start+1，因为方法包左不包右，因此end不需要- 1
        return String.valueOf(chars).substring(start+1,end);
    }


    public static void main(String[] args){
        String str = "babad";
        System.out.println(longestPalindrome(str));
    }
}
